package com.lss.d_substr;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lss
 * @description 最小覆盖子串
 * @createDate 2024/12/6-8:33
 */
public class lc_76 {
    public static void main(String[] args) {

    }

    /**
     * 获取字符串中包含t的最小子串
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        char[] chars = t.toCharArray();
        Map<Character, Integer> tarMap = new HashMap<>(t.length());
        for (char x : chars) {
            tarMap.compute(x, (k, v) -> (v == null) ? 1 : v + 1);
        }
        Map<Character, Integer> windowMap = new HashMap<>();
        int left = 0;
        int right = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        int matched = 0;
        int required = tarMap.size();
        while (right < s.length()) {
            // 加入进集合中
            char c = s.charAt(right);
            if (tarMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                // 数值匹配
                if (windowMap.get(c).equals(tarMap.get(c))) {
                    matched++;
                }
            }
            right++;
            // 移除元素
            while (left < right && matched == required) {
                if (right - left < minLen) {
                    minLen = right - left;
                    minLeft = left;
                }
                char c1 = s.charAt(left);
                if (tarMap.containsKey(c1)) {
                    windowMap.put(c1, windowMap.get(c1) - 1);
                    if (windowMap.get(c1) < tarMap.get(c1)) { // 修复点：正确减少matched计数
                        matched--;
                    }
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }


    public String minWindow_ai(String s, String t) {
        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        int requiredSize = targetMap.size(); // 需要匹配的字符种类数
        Map<Character, Integer> windowMap = new HashMap<>(); // 窗口中字符出现的次数
        int left = 0; // 窗口左边界
        int right = 0; // 窗口右边界
        int minLen = Integer.MAX_VALUE; // 最小覆盖子串的长度
        int minLeft = 0; // 最小覆盖子串的起始位置
        int matched = 0; // 窗口中已匹配的字符种类数

        while (right < s.length()) {
            char c = s.charAt(right);
            // 扩展窗口，加入右边界字符
            if (targetMap.containsKey(c)) {
                windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
                if (windowMap.get(c).equals(targetMap.get(c))) {
                    matched++;
                }
            }
            right++;
            // 尝试收缩窗口，移动左边界
            while (matched == requiredSize) {
                // 更新最小覆盖子串
                if (right - left < minLen) {
                    minLen = right - left;
                    minLeft = left;
                }
                char leftChar = s.charAt(left);
                // 收缩窗口，移出左边界字符
                if (targetMap.containsKey(leftChar)) {
                    if (windowMap.get(leftChar).equals(targetMap.get(leftChar))) {
                        matched--;
                    }
                    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }

}
